This invention relates generally to data computer database visualization and searching, and more particularly, to a method and apparatus for updating a multidimensional scaling database.
The representation of similarity between objects is of great interest in human vision, in image processing, and in computer vision. Quite recently, Cutzu and Edelman reported on results which inferred that humans perhaps organize objects for recognition based on similarities. Their notion is that a xe2x80x9cpattern of proximitiesxe2x80x9d modeled an object in an internal representation space. See Cutzu, F. and S. Edelman, xe2x80x9cRepresentation of object similarity in human vision: psychophysics and a computational modelxe2x80x9d. Vision Research 38(15/16), 1998, pp. 2229-2257. In addition, T. Kohonen has for years worked on a model, the self-organizing feature map, that clusters data while preserving the topological arrangement of the clusters. Kohonen""s arguments are based on biologically plausible notions. See Kohonen, T. Self-Organizing Maps, 2nd ed. New York: Springer-Verlag, 1997; Tipping, M. E. xe2x80x9cTopographic Mappings and Feed-Forward Neural Networks.xe2x80x9d Ph.D. Thesis, University of Aston in Birmingham, February 1996.
Representations of object similarity in Cutzu and Edelman were visualized using Multidimensional Scaling (MDS), a technique where the relative locations of a set of nodes in a low dimensional (with respect to the size of the set) space are sought, given information that may be interpreted as distances. This follows the use of MDS for arranging images for visualization (Tomasi et al.) or to determine human perceptions of their relationships (Rogowitz et al.). See Rogowitz, B., T. Frese, J. R. Smith, and C. A. Bouman xe2x80x9cPerceptual Image Similarityxe2x80x9d, Human Vision and Electronic Imaging II, SPIE Proceedings 3299, 1998.
Multidimensional scaling (MDS) is a technique used for representing many types of data in a spatial arrangement that is generated from dissimilarity or similarity data. The dissimilarity data is put into a matrix of values which represent distances between data nodes, and then the configuration of data in space which most closely fits the matrix of values is looked for, by using a minimization procedure. Because all of the data is used in the minimization procedure at one time, the procedure is slow when applied to a large set of data nodes. In most MDS techniques, when a data node is added the entire matrix of values is used to recompute the configuration again. The computation technique, which at minimum involves a least squares solution, is therefore order O(n3) with respect to the number of data nodes, for a fixed number of iterations. Because MDS produces optimal results, database designers typically wish to use this technique for organizing the data in a database of images, some of which may contain thousands of images. However, a procedure of order O(n3) is generally unacceptable for even modest sized databases. This has been noted by others who have given methods for doing an acceptable job without using the MDS technique, in order to reduce the computational time. For example, see Faloutsos, C. and K. I. Lin., xe2x80x9cFastMap: A Fast Method for Indexing. Datamining and Visualization of Traditional and Multimedia Datasets.xe2x80x9d SIGMOD, 1995, pp. 163-174; and Tipping, M. E., xe2x80x9cTopographic Mappings and Feed-Forward Neural Networksxe2x80x9d, Ph.D. Thesis, University of Aston in Birmingham, February 1996.
Because of the considerations described above, there is a need for a way to update a new node in a MDS database which can be performed in a computationally efficient manner, preferably in order O(n) time or better.
The present invention provides a method, apparatus and article of manufacture for updating a new node in a multidimensional scaling (MDS) database having an existing node. The new node is compared to the existing node to obtain a disparity value. A distance value is calculated between the new node and the existing node, a sum of differences value is calculated for the disparity value and the distance value, and a sum of squares value is calculated for the disparity value and the distance value. The position of the new node is modified according to the sum of differences value and the sum of squares value.